//
// Created by Administrator on 2023/11/23.
//
#include "bits/stdc++.h"

using namespace std;

const int N=210,INF=0x3f3f3f3f;

int g[N][N];
int n,m;

void floyd(){
    //注意k在最外层
    for (int k = 1; k<=n; ++k) {
        for (int j = 1; j <=n; ++j) {
            for (int i = 1; i <= n; ++i) {
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}

int main(){
    int k;
    memset(g,INF,sizeof g);
    for (int i = 0; i <= n; ++i) {
        g[i][i]=0;
    }
    cin>>n>>m>>k;
    for (int i = 0; i < m; ++i) {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=z;
    }
    floyd();
    while(k--){
        int x,y;
        cin>>x>>y;
        //有负边存在。就得用>
        if(g[x][y]>INF/2) cout<<"impossible"<<endl;
        else cout<<g[x][y]<<endl;
    }
}